package 程序员面试金典;

public class 最大子矩阵 {

  /**
    i,j双指针遍历所有可能的的两个“行对”，即子矩阵的上下两条边，这决定了矩阵的高
    将i-j之间的每一列（求出每一列的累计的和）看成一维数组中的一项，在其中求最大子数组，即求出符合的子矩阵的宽
 */
  public int[] getMaxMatrix(int[][] matrix) {
      int m=matrix.length;
      int n=matrix[0].length;
      int[][] preSum=new int[m+1][n];
      int max=matrix[0][0];
      int[] res=new int[4];
      for (int i = 1; i < m+1; i++) {
          for (int j = 0; j < n; j++) {
              preSum[i][j]=preSum[i-1][j]+matrix[i-1][j];
          }
      }
      for (int top = 0; top < m; top++) {
          for (int bottom = top; bottom < n; bottom++) {
              //找到连续子数组的最大值
              int[] ints = new int[n];
              for (int i = 0; i < n; i++) {
                  ints[i]=preSum[bottom+1][i]-preSum[top][i];
              }
              int start=0;
              int sum=ints[0];
              for (int i = 1; i <n; i++) {
                  if (sum>0)
                      sum+=ints[i];
                  else {
                      sum=ints[i];
                      start=i;
                  }
                  if (sum>max){
                      max=sum;
                      res[0]=top;
                      res[1]=start;
                      res[2]=bottom;
                      res[3]=i;
                  }
              }
          }
      }
      return res;
  }

}
